Given two sequences, find the length of longest subsequence present in both of them. Both the strings are of uppercase. Example 1: Input: A = 6, B = 6 str1 = ABCDGH str2 = AEDFHR Output: 3 Explanation: LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3. Example 2: Input: A = 3, B = 2 str1 = ABC str2 = AC Output: 2 Explanation: LCS of "ABC" and "AC" is "AC" of length 2.

---

        Code


  #include <bits/stdc++.h>
  using namespace std;
         
int lcs(string x,string y,int m,int n)
{
    int dp[m+1][n+1],i,j;
    for(i=0;i<m+1;i++)
    {
        for(j=0;j<n+1;j++)
        {
            if(i==0||j==0)
             dp[i][j]=0;
        }
    }
     for(i=1;i<m+1;i++)
    {
        for(j=1;j<n+1;j++)
        {
            if(x[i-1]==y[j-1])
             dp[i][j]=dp[i-1][j-1]+1;
            else
             dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    return dp[m][n];
}
int main()
 {
  string x,y;
	    int m,n;
	     cin>>m>>n;
	    cin>>x>>y;
	    
	    cout<<lcs(x,y,m,n);
	    
 
	return 0;
}